The present invention generally relates to an improved dynamic assignment protocol, more particularly relates to improvements to receiver directed broadcast schemes, and even more particularly relates to implicit reservation and optimized scheduling techniques for receiver directed broadcast schemes.
Mobile multi-hop packet radio networks are known for rapid and convenient deployment, self-organization, mobility, and survivability. Such a network is illustrated in FIG. 1. A transmission from one node, from node N1 of FIG. 1 for example, can be broadcast to all nodes in its xe2x80x9cneighborhood.xe2x80x9d Ultra-high frequency (UHF) systems generally have a neighborhood defined by nodes located within line of sight of the transmitting node. The nodes of such a neighborhood are said to be located within one xe2x80x9chopxe2x80x9d of the transmitting node. In FIG. 1, for example, nodes N1, N3, N4, N5, N6, N7 and N8 are members of the neighborhood surrounding node N1.
Nodes N2, N9, N10, N11 and N12 are each located two hops away from node N1 and node N13 can be said to be three hops away from node N1. When data transmitted from node N1 is to be propagated multiple hops, the data must be relayed by one or more of node N1""s neighbors. For example, data transmitted by node N1 can be relayed by its neighbor node N8 to a node such as node N12 that is located two hops from node N1.
Receivers are generally capable of processing only one transmission at a time. When using such receivers, simultaneous transmissions (also known as collisions, contentions or conflicts) can be avoided by assigning a specific transmission time slot to each communicating node. Several approaches have been developed for assigning slots to nodes. The approach chosen for a particular application is generally a consequence of the type of network application (broadcast, multicast, unicast, datagrams, virtual circuits, etc.) at issue. Since the problem of optimally assigning slots is mathematically intractable, a heuristic approach has been applied. This approach resulted in the development of an integrated protocol that both chooses the number of slots to assign to each neighboring node and coordinates their activation in the network.
Many applications require self-organizing, wireless networks that can operate in dynamic environments and provide peer-to-peer, multi-hop, multi-media communications. Key to this technology is the ability of neighboring nodes to transmit without interference. Neighboring nodes transmit without interference by choosing time slots and channels that do not cause collisions at the intended unicast or multicast receivers.
The Unifying Slot Assignment Protocol (USAP), which is disclosed in U.S. Pat. No. 5,719,868, provides a protocol establishing such a communication system. USAP is a dynamic assignment protocol that monitors the RF environment and allocates channel resources on demand. It automatically detects and resolves contention between nodes for time slots, such contention arising for example from changes in connectivity. U.S. Pat. No. 5,719,868, issued Feb. 17, 1998, is hereby incorporated herein by reference in its entirety, including all drawings and appendices.
USAP permits a node to assign itself transmit slots based on information it has regarding when it is assigned to transmit and receive and when a neighboring node is scheduled to transmit. In one embodiment of USAP, receiver directed broadcast (RDB), a node can assign itself a receive slot instead of a transmit slot. For example, a node may need to assign itself a receive slot wherein it can receive from one, some or even all of its neighbors. This receiver directed type of assignment is disclosed in application Ser. No. 09/552,144, filed Apr. 19, 2000. The specification, including all drawing figures, of application Ser. No. 09/552,144, filed Apr. 19, 2000, is hereby incorporated herein by reference in its entirety.
There exists a need for further refinements and improvements to dynamic assignment protocol based systems using RDB. In particular, there exists a need for a technique that can implicitly reserve slots, for use in virtual circuits for example. In explicit reservation techniques, slots are taken from idle transmitters and are explicitly reassigned to nodes needing additional transmit capacity. In various applications, however, the use of explicit reservations can lead to an inefficient use of communication resources. Voice or video transmission applications, for example, can often tolerate a degree of initial packet loss and delay.
There is also a need to maximize throughput in systems using RDB schemes. For example, there exists a need for an optimized RDB scheduling technique that is capable, under heavy uniform traffic and for a given number of nodes and channels, of keeping each node busy all of the time. These needs are addressed and fulfilled by the detailed description provided below.
It is an object of the present invention to provide an improved technique for reserving slots in a receiver directed broadcast environment.
It is a feature of the present invention to utilize an implicit reservation of communication slots.
It is an advantage of the present invention to bring about a significant reduction of overhead by reducing the size of the control packet.
It is another object of the present invention to provide an improved technique for scheduling transmissions in a receiver directed broadcast environment.
It is another feature of the present invention to utilize an optimized RDB scheduling technique.
It is another advantage of the present invention to enable attainment of maximized throughput by keeping substantially every node busy transmitting or receiving nearly all of the time.
Thus, the present invention involves improved receiver directed broadcast systems and methods. The improvements can be carried out in an efficient, xe2x80x9cwaste-lessxe2x80x9d manner in the sense that throughput can be maximized or control overhead can be minimized. As noted herein, and as will be appreciated, the invention has several useful and valuable applications.